package OfferLanQiaoBei.a_12届蓝桥真题;

import java.util.Scanner;

/*
给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n)，即 ai=i
小蓝将对这个序列进行 m 次操作，每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列，或者将 aqi,aqi+1,⋅⋅⋅,an 升序排列。
请求出操作完成后的序列。

输入格式
输入的第一行包含两个整数 n,m，分别表示序列的长度和操作次数。
接下来 m行描述对序列的操作，其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。
当 pi=0 时，表示将 a1,a2,⋅⋅⋅,aqi 降序排列；当 pi=1 时，表示将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

输出格式
输出一行，包含 n 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

数据范围
对于 30%的评测用例，n,m≤1000；
对于 60% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤10e5，0≤pi≤1，1≤qi≤n

输入样例：

3 3
0 3
1 2
0 2

输出样例：

3 1 2

样例解释
	原数列为 (1,2,3)
	
	第 1步后为 (3,2,1)
	
	第 2步后为 (3,1,2)
	
	第 3步后为 (3,1,2)。
	与第 2 步操作后相同，因为前两个数已经是降序了。
 */
public class i双向排序 {
    public static void main(String[] args) {
		i双向排序 test = new i双向排序();
		test.useDeal();
	}
    
    public void useDeal() {
    	Scanner scanner = new Scanner(System.in);
    	int N = scanner.nextInt();
    	int m = scanner.nextInt();
    	int top = 0;
    	PII[] stk = new PII[m + 1];
    	int[] res = new int[N + 1];
    	while (m-- > 0) {//制作栈
    		//收集当前操作A的数据
			int status = scanner.nextInt();
			int index = scanner.nextInt();
			if (status == 0) {//当前的当前的操作是：前缀操作
				//------从这里
				while (top != 0 && stk[top].status == 0) {//不是空栈，并且栈顶元素B是前缀操作
					index = Math.max(index, stk[top].index);//取A与B最长的其中一个
					top--;//指针top下移；设此时的top为Dtop；循环结束的结果就是现在的Dtop指向的是一个后缀操作
				}
				while (top >= 2 && stk[top - 1].index <= index) {//当前栈有足够多元素(即最少有一对前缀后缀操作)；Dtop - 1指向的才是一个前缀操作C，如果C的长度比Max(前面遍历的所有的前缀操作)短
					top -= 2;//此时Dtop指向后缀操作；-=的目的是弹栈；被减走的元素就相当于被弹出去
				}
				//------到这里，是优化；压缩前缀操作
				stk[top + 1] = new PII(0, index);//Dtop+1，那么就指向了当前栈中栈顶的操作；覆盖当前操作，即存入栈中
				top++;//把Dtop现在经过了++操作后的指向的位置，当作栈顶
			} else if (top != 0) {//当前的当前的操作是：后缀操作
				while (top != 0 && stk[top].status == 1) {//不是空栈，并且栈顶元素B是后缀操作
					index = Math.min(index, stk[top].index);
					top--;
				}
				while (top >= 2 && stk[top - 1].index >= index) {
					top -= 2;
				}
				stk[top + 1] = new PII(1, index);
				top++;
			}
		}
    	deal(stk, res, N, top);
    }
    
    public void deal(PII[] stk, int[] res, int N, int top) {
    	int useToSaveFromOriginArr = N;//用来从原数组中，拿取对应位置的数字，填入res[]中的帮助指针
    	int l = 1;//左端点
    	int r = N;//右端点
    	for (int i = 1; i <= top; i++) {//这个循环就开始填充res[]了
			if (stk[i].status == 0) {
				while (r > stk[i].index && l <= r) {
					res[r--] = useToSaveFromOriginArr--;
				}
			} else {
				while (l < stk[i].index && l <= r) {
					res[l++] = useToSaveFromOriginArr--;
				}
			}
			if (l > r) {//没有了重合部分，直接填完了；这里画图理解很到位；用牙签代表指针
				break;
			}
		}
    	if (top % 2 == 1) {//当栈里的所有前后缀，都操作完了，最后一对前后缀仍然存在重叠区间；就会走这个判断；所有前缀的top都是奇数，不信去画图
			while (l <= r) {
				res[l++] = useToSaveFromOriginArr--;
			}
		} else {//所有后缀操作的top都是偶数
			while (l <= r) {
				res[r--] = useToSaveFromOriginArr--;
			}
		}
    	for (int i = 1; i <= N; i++) {
    		if (i == N) {
    			System.out.println(res[i]);
    			return;
			}
			System.out.print(res[i] + " ");
		}
    }
    
    private static class PII {
    	int status;
    	int index;
    	public PII(int status, int index) {
    		this.status = status;
    		this.index = index;
    	}
    }
}
